/*
 * @lc app=leetcode.cn id=239 lang=javascript
 *
 * [239] 滑动窗口最大值
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
// var maxSlidingWindow = function(nums, k) {
//   const q = [];
//   let result = [];

//   // for (let i = 0; i < k; i++) {
//   //   const num = nums[i];
//   //   while(q.length && num > nums[q[q.length -1]]){
//   //     q.pop();
//   //   } 
//   //   q.push(i);
//   // }
//   // result.push(nums[q[0]]);

//   for (let i = 0; i < nums.length; i++) {
//     const num = nums[i];
//     // 比num小的都扔掉
//     while(q.length && num > nums[q[q.length -1]]){
//       q.pop();
//     }
//     q.push(i);
//     while (q[0] <= i - k) { 
//       q.shift(); 
//     }
//     i >= k-1 && result.push(nums[q[0]]);
//   }
//   return result;
// };

var maxSlidingWindow = function(nums, k) {
  const q = [];
  let result = [];

  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    // 比num小的都扔掉
    while(q.length && num > nums[q[q.length -1]]) q.pop();
    q.push(i);
    if( i - q[0] == k) q.shift(); 
    if(i + 1 >= k) result.push(nums[q[0]]);
  }
  return result;
};
// @lc code=end

